矩阵
- 旋转
from copy import deepcopy
def rotate90(m):
el_len = len(m[0])
new_m = [[0]*len(m) for _ in range(el_len)]
for i, row in enumerate(m):
for j, elem in enumerate(row):
new_m[el_len-1-j][i] = elem
return new_m
def rotate180(m):
for row in m:
row = row.reverse()
return m
def rotate270(m):
new_m = [[0]*len(m) for _ in range(len(m[0]))]
for i, row in enumerate(m):
for j, elem in enumerate(row):
new_m[j][i] = elem
return new_m
if __name__ == "__main__":
m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
m1 = deepcopy(m)
assert rotate90(m1) == [[4, 8, 12], [3, 7, 11], [2, 6, 10], [1, 5, 9]]
m1 = deepcopy(m)
assert rotate180(m1) == [[4, 3, 2, 1], [8, 7, 6, 5], [12, 11, 10, 9]]
m1 = deepcopy(m)
assert rotate270(m1) == [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]
- 炸弹人
Given a 2D grid, each cell is either a wall 'W',
an enemy 'E' or empty '0' (the number zero),
return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from
the planted point until it hits the wall since the wall is too strong
to be destroyed.
Note that you can only put the bomb at an empty cell.
Example:
For the given grid
0 E 0 0
E 0 W E
0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)
思路： 逐一查看行和列
import numpy as np
def bomb_row(row, index):
kills = 0
step = index
while step > 0:
step -= 1
if row[step] == "e":
kills += 1
elif row[step] == "w":
break
step = index
while step < len(row)-1:
step += 1
if row[step] == "e":
kills += 1
elif row[step] == "w":
break
return kills
def bomb_enemy(grid):
kills = 0
for i, row in enumerate(grid):
for j, elm in enumerate(row):
if elm == "0":
kills = max(kills, bomb_row(row, j)+bomb_row(grid[:, j], i))
return kills
if __name__ == "__main__":
grid = np.asarray([[0, "e", 0, 0, "e"],
["e", 0, "e", "w", "e"],
[0, "e", 0, 0, 0],
[0, "e", 0, 0, 0]
])
assert bomb_enemy(grid) == 5
- 稀疏矩阵点乘
"”” Given two sparse matrices A and B, return the result of AB. You may assume that A’s column number is equal to B’s row number. Example: A = [ [ 1, 0, 0], [-1, 0, 3] ] B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 | "””
思路：找出非零的然后计算
import numpy as np
def multiply(a, b):
ar, ae = a.shape
br, be = b.shape
assert ae == br
c = np.zeros([ar, be])
for i, arow in enumerate(a):
for j, aelem in enumerate(arow):
if aelem:
for k, belem in enumerate(b[j]):
if belem:
c[i, k] += belem*aelem
return c
if __name__ == "__main__":
a = np.array([[1, 0, 0],
[-1, 0, 3]])
b = np.array([[7, 0, 0],
[0, 0, 0],
[0, 0, 1]])
print(multiply(a, b))
- 旋转遍历
"”” Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. "””
思路：分方向，给出起始坐标，不停更新矩阵
import numpy as np
def skip(matrix, direction, i, j, res):
n, m = matrix.shape
if direction == 0:
while j < m:
res.append(matrix[i, j])
j += 1
matrix = matrix[i+1:, :]
n, m = matrix.shape
return matrix, 0, m-1, 1
elif direction == 1:
while i < n:
res.append(matrix[i, j])
i += 1
matrix = matrix[:, :m-1]
n, m = matrix.shape
return matrix, n-1, m-1, 2
elif direction == 2:
while j >= 0:
res.append(matrix[i, j])
j -= 1
matrix = matrix[:n-1, :]
n, m = matrix.shape
return matrix, n-1, 0, 3
else:
while i >= 0:
res.append(matrix[i, j])
i -= 1
return matrix[:, j+1:], 0, 0, 0
def spiral_traversal(matrix):
res, direction = [], 0
n, m = matrix.shape
i, j = 0, 0
while len(res) < n*m:
matrix, i, j, direction = skip(matrix, direction, i, j, res)
return res
if __name__ == "__main__":
mat = np.asarray([[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]])
assert spiral_traversal(
mat) == [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
- 计算路径
"”” Count the number of unique paths from a[0][0] to a[m-1][n-1] We are allowed to move either right or down from a cell in the matrix. Approaches- (i) Recursion- Recurse starting from a[m-1][n-1], upwards and leftwards, add the path count of both recursions and return count. (ii) Dynamic Programming- Start from a[0][0].Store the count in a count matrix. Return count[m-1][n-1] T(n)- O(mn), S(n)- O(mn) "””
思路：和爬梯子一样，斐波那契数
import numpy as np
def count_paths(m, n):
if m < 1 or n < 1:
return -1
count = np.zeros((n, m))
count[0, :] = 1
count[:, 0] = 1
for i in range(1, n):
for j in range(1, m):
count[i, j] = count[i, j-1] + count[i-1, j]
return count[-1, -1]
if __name__ == "__main__":
assert count_paths(3, 4) == 10
